import java.util.Arrays;

/**
 * @Classname KMP
 * @Description 常用于字符串匹配问题
 * @Date 2021/12/23 14:27
 * @Created K024851
 */
public class KMP {

    public static void main(String[] args) {
        String s1 = "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        int next[] = kmpNext(s2);
        System.out.println(Arrays.toString(next));
        int index = kmpSearch(s1,s2,next);
    }
    //暴力匹配
    public static int violenceMach(String str1,String str2){
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int s1Len = s1.length;
        int s2Len = s2.length;
        int i = 0;
        int j = 0;
        while (i<s1Len && j<s2Len){
            if (s1[i] ==s2[i]){
                i++;
                j++;
            }else {
                i = i-(j-1);
                j=0;
            }
        }

        if (j ==s2Len){
            return i-j;
        }else {
            return -1;
        }
    }

    //KPM 算法
    public static int kmpSearch(String str1,String str2,int[]next){
        for (int i = 1,j =0;i<str1.length();i++){
            while (j>0&& str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if (str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if (j== str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }

    public static int[] kmpNext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i =1,j=0;i<dest.length();i++){
            while (j>0&& dest.charAt(i)!= dest.charAt(j)){
                j = next[j-1];
            }
            if(dest.charAt(i) ==dest.charAt(j) ){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
